package d26

import "sort"

func earliestSecondToMarkIndices(nums []int, changeIndices []int) int {
	if len(nums) > len(changeIndices) {
		return -1
	}
	if !IsEnoughMarkIndices(nums, changeIndices) {
		return -1
	}

	leftIdx := len(nums) + 1
	rightIdx := len(changeIndices) - 1
	for leftIdx < rightIdx {
		midIdx := (leftIdx + rightIdx) / 2
		if IsEnoughMarkIndices(nums, changeIndices[0:midIdx]) {
			rightIdx = midIdx
		} else {
			leftIdx = midIdx + 1
		}
	}

	return rightIdx
}

func IsEnoughMarkIndices(nums []int, changeIndices []int) bool {
	latestChange := make(map[int]int, len(nums))
	for idx, changeIdx := range changeIndices {
		latestChange[changeIdx-1] = idx
	}

	sortNumsIdx := make([]int, len(nums))
	for idx, _ := range nums {
		sortNumsIdx[idx] = idx
	}
	sort.Slice(sortNumsIdx, func(i, j int) bool {
		return latestChange[sortNumsIdx[i]] < latestChange[sortNumsIdx[j]]
	})

	remainCount := 0
	for idx, changeIdx := range changeIndices {
		innerChangeIdx := changeIdx - 1
		if latestChange[innerChangeIdx] == idx {
			if remainCount > nums[innerChangeIdx] {
				remainCount = remainCount - nums[innerChangeIdx]
				continue
			} else {
				return false
			}
		}
		remainCount = remainCount + 1
	}
	return true
}
